﻿'''
力扣21：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
'''
class Node:
    def __init__(self,val):
        self.val = val
        self.next = None

def merge_two_list(l1,l2)-> Node:
        if not l1:
            return l2
        if not l2:
            return l1
        cur_l1 = l1
        cur_l2 = l2
        result = Node(0)
        head = result
        while cur_l1 and cur_l2:
            if cur_l1.val <= cur_l2.val:
                result.next = cur_l1
                result = result.next
                cur_l1 =cur_l1.next
            else:
                result.next = cur_l2
                result = result.next
                cur_l2 = cur_l2.next
        if not cur_l1:
            result.next = cur_l2
        else:
            result.next = cur_l1
        return head.next
#示例
if __name__ == '__main__':
    head = Node(1)
    head.next = Node(2)
    head.next.next= Node(4)
    l2 = Node(1)
    l2.next = Node(3)
    l2.next.next = Node(4)
    new_head = merge_two_list(head,l2)
    while new_head:
        print(new_head.val,end= ' ')
        new_head = new_head.next